1. Field of the Invention
This invention relates to a video device which employs error correction on digital signals representing audio and video data. The video device includes an encoder, a decoder and a noise level detector. The noise level detector identifies noise at select data word times (i.e., locations) within the encoded signal, and thereafter forwards the identified locations to a block decoder. The identified data locations are used as a basis for increasing the performance by which correction is achieved within the block decoder.
2. Description of the Relevant Art
Error correction of digital data is well known in the field of audio and video reproduction and storage. Error correction is typically used both to restore digital information which has in some way been disrupted or lost during recordation and/or transmission. Error correction makes digital data storage and transmission much more robust than counterpart analog systems. Accordingly, error correction proves beneficial in relaxing the manufacturing tolerances of memory media as well as reducing the power and costs requirements of the transmitter and receiver.
High recording densities and unfriendly transmission environments necessitate a sophisticated error correction scheme. Errors imputed upon the digital signals generally arrive from possibly three sources: the digital recordation and reproduction system, the storage media, and/or the transmission channel interference. It is well known that recordation and reproduction errors such as aliasing and quantization affect the accuracy by which digital signals are represented. Irregularities on the storage media surface and noise (interference) placed on the transmission channel further disrupt the digital signals. Regardless of their source, errors are generally classified as random errors or burst errors. As the name implies, random errors occur in random fashion and generally have no relation to one another. Conversely, a burst error is one which occurs over a relatively long period of time and often involves the disruption of perhaps hundreds, if not thousands of bits. Burst errors may have various causes. In memory media, a burst error may be caused by a large dust particle resting on the surface of the medium. In a transmission channel, a burst error may be caused by channel fading or may be caused by periodic noise imputed on the channel. Regardless of the cause, burst errors are a commonly occurring kind of error which, due to their extended duration, pose a greater challenge to error correction than random errors.
Error correction is employed in correction of burst errors, but more importantly must do so with a minimal amount of redundant data and data processing. Reducing the probability of bit error is one of the main functions of error correction modules. A successful error correction technique can perform the aforesaid advantages not only to detect the location of errors but to correct those error locations.
Error detection and correction are brought about, in a general sense, by coding. The use of large-scale integrated (LSI) circuits has made it possible to provide substantial performance improvement through coding. Coding, and the advantages thereof, are achieved on the integrated circuit at much less cost than would be necessary if higher-power transmitters or larger antennas were used. There are a number of types of coding techniques used for error detection and correction. The two very frequently used types are block coding and convolutional coding. Block and convolutional coding serve to find errors within a sequence of structured codewords and, thereafter, to correct erroneous words within that sequence.
A sequence of structured codewords involves an information stream with additional redundant information. The codewords are composed of symbols, and the symbols can be as small as a single bit or can contain numerous bits (or a byte) of digital information. Accordingly, codewords are set forth in a code, and code can be either bit-oriented code or byte-oriented code depending upon whether the code word is represented as a plurality of single-bit symbols or a plurality of eight-bit symbols, respectively.
Error correction involves not only the detection of errors, but also correction of those errors. While block coding entails codewords formed of a block of symbols (data and check symbols) placed in a structured sequence arranged solely from the message contained in the block, convolutional coding entails a structured sequence of codewords formed from the message present in the encoder at that time, including previous messages as well. Regardless of whether block or convolutional coding is used, the resulting codeword sequence, involving data symbols and check symbols, is decoded by an error correction algorithm.
There are several types of block coding algorithms. Many of them concern the popular Reed-Solomon codes, which may be defined as block codes whose check symbols are determined by polynomial operations in a Galois field with a generator polynomial formed by multiplying monomials whose roots are consecutive elements in the field. Reed-Solomon codes are popular since the encoding can be performed by using the generator polynomial to multiply or divide a polynomial representing the message. Furthermore, low complexity methods exist for error correcting received symbol blocks. One popular decoding algorithm involves determining polynomials with roots that locate errors, and generating syndromes to correct errors. In this manner, the data symbols and check symbols within a codeword may be algebraically combined with one another to determine if a data symbol is erroneous. Determination of the erroneous data symbol location is taken from an algebraic sum of the roots. A polynomial expansion of those roots allows the Reed-Solomon algorithm to thereafter correct the data symbol location. Both detection and correction occurs within the conventional Reed-Solomon decode algorithm. The Reed-Solomon decode algorithm, and the methodology by which polynomials and roots allow detection and correction of errors, is provided and referenced in B. Sklar, Digital Communications Fundamentals and Applications, (Prentice Hall 1988), pp. 304-308 (herein incorporated by reference).
Unlike block coding, codeword output n-tuple of a convolutional encoding procedure is not only a function of an input k-tuple, but is also a function of the previous K-1 input k-tuples. As such, convolutional codes are often referred to as recurrent codes.
Generally speaking, a convolutional encoder may be implemented using a shift register and a plurality of encoder vectors, one for each codeword symbol. Each codeword symbol is then generated by the inner product of the corresponding encoder vector and the contents of the shift register. For example, a bit-oriented encoder might use two binary vectors to generate a two bit codeword by multiplying the contents of the shift register with each vector component-wise, and perform the sum using modulo two addition. Two code symbols are thereby generated and paired together to form a codeword. The memory of the convolutional encoder is determined by the length of the shift register, and in general, a larger memory can provide a larger coding gain. Convolutional encoding and subsequent Viterbi decoding are well documented algorithms. See, e.g., B. Sklar, Digital Communications Fundamentals and Applications, (Prentice Hall 1988), pp. 315-338 (herein incorporated by reference).
The performance of block encoders/decoders are especially dependent on their ability to efficiently use check symbols to reconstruct incorrect or lost data symbols. When multiple symbol errors are sustained, as in the case of a burst error, both the data symbol and the associated check symbol may be affected. To reduce the impact of this, data symbols within each codeword (or codewords amongst each other) are dispersed throughout the data stream (i.e. interleaved) before the data is recorded or transmitted. If a burst error occurs, it damages only a reproducible portion of data symbols but not all data symbols within the codeword. Upon playback the code is de-interleaved. Thus, the data symbols return to their original codeword location (i.e., to the original structured codeword) with errors properly distributed therein. Interleaving and subsequent de-interleaving greatly increases error correctability of block codes by separating each symbol from its pre-interleaved neighbors by a span of several symbols. An error occupying several data symbol intervals will affect one data symbol per codeword instead of possibly numerous pre-interleaved neighboring data symbols.
Error correction is greatly enhanced by utilizing block coding, convolutional coding and interleaving. A device which employs all three techniques in a concatenated architecture not only reduces power and bandwidth requirements, but can do so beyond that which would be required using either block or convolutional coding individually. A concatenated Reed-Solomon outer code and a convolutional inner code serves to reduce E.sub.b /N.sub.0 while achieving less than 1.times.10.sub.-12 bit error probability. While the Viterbi decoder may output burst errors, those errors are de-interleaved before entering the Reed-Solomon decoder. The Reed-Solomon decoder depends only on the number of data word errors within a block of codewords, with minimal disturbance by burst errors. The concatenated architecture is often motivated in systems which employ high speed digital signals.
As systems evolve to higher signal processing speeds due to higher information storage densities and/or higher information transmission rates, encoders which can provide improved error correction performance will be required. For example, video data is oftentimes compressed with a high bit rate which necessitates a higher speed decoder, and a decoder which can correct more errors than conventional decoders. It is often the case that the requirement for improved performance, which typically involves substantial increases in device complexity, is accompanied by the requirement for higher throughput speeds and lower decoding delays.